/*Copyright (c) Microsoft Open Technologies, Inc.  All rights reserved.
Microsoft Open Technologies would like to thank its contributors, a list
of whom are at https://interview.codeplex.com/team/views.

Licensed under the Apache License, Version 2.0 (the "License"); you
may not use this file except in compliance with the License. You may
obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied. See the License for the specific language governing permissions
and limitations under the License.*/

/*
Problem: use an array to represents a tree (a general tree, not binary tree), the value of array item
         represent the parent id for that item and the root's parent is -1. 
         e.g. A[0..5] = {1, 2, 3, -1, 2, 2}
         The root of this tree is index 3 of this array, and the tree graph looks like as below:
                3:-1
               /
              2:3
            /  |  \
          1:2  4:2  5:2
          /
        0:1

        3:-1, 3 means the index (its id) in the array, and -1 is the parent id/index

        The problem is to get the level of that tree, in this case it's 4.
*/

// Compile it by: g++ -Wall -std=c++0x tree_level.cpp

#include <assert.h>
#include <iostream>
#include <functional>
using namespace std;

class get_tree_level{
public:
    get_tree_level(int *nodes, int count) : n(count) {
        tree = new int[n];
        levels = new int[n];
        for (int i=0; i<n; i++) {
            tree[i] = nodes[i];
            levels[i] = 0;
        }
    }

    ~get_tree_level() {
        delete[] tree;
        delete[] levels;
    }

    int operator()() {
        int max = 0;
        std::function<int(int)> get_level;
        get_level = [&] (int i) -> int {
            assert (i >= 0 && i < n);

            if (!levels[i]) {
                if (tree[i] == -1)
                    levels[i] = 1;
                else
                    levels[i] = get_level(tree[i]) + 1;
            }

            return levels[i];
        };

        for (int i=0; i<n; i++) {
            if (get_level(i) > max) {
                max = get_level(i);
            }
        }

        return max;
    }
private:
    int *tree;
    int *levels;
    int n;
};

int main() {
    int arr[] = { -1, 0, 0, 1, 1, 2, 5 };
    int count = sizeof(arr) / sizeof(int);
    get_tree_level tree_level(arr, count);
    cout << "tree level: " << tree_level() << endl;
}